package MonotonicStack;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Stack;

/**
 * 503.下一个更大的元素||
 * 给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
 * 数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
 */
public class nextGreaterElements {

    /**
     * 一刷
     */
    //for循环遍历两次
    public int[] nextGreaterElements(int[] nums) {
        int size = nums.length;
        int[] result = new int[size];//存放结果
        Arrays.fill(result, -1);//默认全部初始化为-1
        if (nums.length == 1 || nums.length == 0) return result;
        Stack<Integer> st = new Stack<>();//栈中存放的是nums中的元素下标
        for (int i = 0; i < 2 * size; i++) {
            while (!st.empty() && nums[i % size] > nums[st.peek()]) {
                result[st.peek()] = nums[i % size];//更新result
                st.pop();//弹出栈顶
            }
            st.push(i % size);
        }
        return result;
    }

    //也是遍历两次
    class Solution {
        public int[] nextGreaterElements(int[] nums) {
            Stack<Integer> stack = new Stack<Integer>();
            int[] result = new int[nums.length];
            Arrays.fill(result, -1);
            if (nums == null || nums.length == 0 || nums.length == 1) return result;
            stack.push(0);
            int i = 1;
            int count=0;
            while (!stack.isEmpty()) {
                if (nums[stack.peek()] >= nums[i]) {
                    stack.push(i);
                } else {
                    while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                        result[stack.peek()] = nums[i];
                        stack.pop();
                    }
                }
                stack.push(i);
                i++;
                if (i == nums.length) {
                    i = 0;
                    count++;
                }
                if(count == 2) break;
            }
            return result;
        }
    }

    /**
     * 二刷
     */
    //构建循环数组
    public int[] nextGreaterElements2(int[] nums) {
        int[] temp = new int[nums.length * 2];
        int[] res = new int[nums.length * 2];
        Arrays.fill(res, -1);
        for (int i = 0; i < temp.length; i++) {
            temp[i] = nums[i % nums.length];
        }
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        for (int i = 1; i < temp.length; i++) {
            while (!stack.isEmpty() && temp[i] > temp[stack.peek()]) {
                int index = stack.pop();
                res[index] = temp[i];
            }
            stack.push(i);
        }
        return Arrays.copyOfRange(res, 0, nums.length);
    }
}
